package engine;
import java.util.Vector;

/**
 * @author Jing Lei Email: jing.lei@hut.fi
 * Quick Sort: Good for large inputs 
 * Divide and Conquer: recurrence
 * Worst-case: big theta n*n
 *  
 */

public class Quicksort implements Constants{
	
	
	
	/*
	 * Constructor 
	 */
	public Quicksort() {
				
	}
	
	
	
	/*
	 * Divide and Conquer: recurrence
	 */
	public static void Quicksort(Chessboard board, Vector moves, int p, int r) {
		if (p < r){
			int q = Partition(board,moves, p, r);
			Quicksort(board, moves, p, q - 1);
			Quicksort(board, moves, q + 1, r);
		}
	}
	
	/*
	 * Partition procedure
	 */
	private static int Partition(Chessboard board, Vector moves, int first, int last){
		Move moveFirst = ((Move)moves.get(last));;
		Move moveCurrent;
		int firstSortValue = moveFirst.moveScore;
		int secondSortValue = 0;
						
		int i = first - 1;

		//create arrays L[1..n1 + 1] and R[1..n2 + 1]
		for (int j = first; j < last; j++){
			moveCurrent = ((Move)moves.get(j));
			secondSortValue = moveCurrent.moveScore;
			if (secondSortValue >= firstSortValue){
				i++;
				//swap A[i] and A[j]
				Object tmp = moves.get(i);
				moves.set(i, moves.get(j));
				moves.set(j, tmp);
			}
		}
		
		//swap A[i+1] and A[r]
		Object tmp = moves.get(i+1);
		moves.set(i+1, moves.get(last));
		moves.set(last, tmp);
	
		return (i + 1);
	}
	
}